package com.breeze.leetcode.interview;

import java.util.HashSet;
import java.util.Set;

/**
 * https://leetcode-cn.com/problems/palindrome-permutation-lcci/
 * 面试题 01.04. 回文排列
 * <p>
 * 核心思想：回文要么是奇对称，要么偶对称，故如果去除重复的字符后，剩余的字符长度最大为1，核心就是怎么去重。
 */
class Solution0104 {
    public boolean canPermutePalindrome(String s) {
        int count = 0;
        int lastLen = s.length();
        // 一开始想到散列表了，但是没想到合适的方法，最后通过replace来去重
        while (s.length() > 0) {
            s = s.replace(s.charAt(0) + "", "");
            int len = s.length();
            if ((lastLen - len) % 2 == 1) {
                count++;
            }
            lastLen = len;
        }
        return count <= 1;
    }

    /**
     * 利用哈希表实现去重，最后通过判断哈希表大小是否<=1，即可判断是否是回文
     * 时间复杂度：O(n)
     * 空间复杂度：O(1)
     */
    public boolean canPermutePalindrome1(String s) {
        Set<Character> set = new HashSet();
        for (char c : s.toCharArray()) {
            if (!set.add(c)) {
                set.remove(c);
            }
        }
        return set.size() <= 1;
    }

    /**
     * 由于ASCII字符最多256个，故可以自己实现散列表，散列函数就是 index = char对应的int值
     * 时间复杂度：O(n)
     * 空间复杂度：O(1)
     */
    public boolean canPermutePalindrome2(String s) {
        // ASCII 码最多256位
        int[] map = new int[256];
        int count = 0;
        for (char c : s.toCharArray()) {
            // 是奇数
            if ((++map[c] & 1) == 1) {
                count++;
            } else {
                count--;
            }
        }
        return count <= 1;
    }
}